/**
 *This file is the intellectual property of the author, Jacques Heunis.
 *It may not be used without specific written permission.
 *
 *This class exists to allow the input of mathematical expressions in String form to be evaluated and an answer calculated.
 *
 *In it's current form it supports (and in fact encourages) the use of an arbitrary (the more the better) number of brackets in an expression
 *
 *@author Jacques Heunis
 */

package mathematitools;

import java.math.BigDecimal;
import java.math.MathContext;

public class ExpressionParser {
    //========================
    //=====Private Classes====
    //========================
    private static class BracketData{
        public int location;
        public int length;
        public boolean isFunction;
        public String function;
        
        public BracketData(int loc, int leng, String functionName){
            location = loc;
            length = leng;
            function = functionName;
            isFunction = (functionName.length()>0);
        }
    }
    
    
    //========================
    //=====Helper Methods=====
    //========================
    
    /**
     *Tests to see if the given character is a mathematical operation.
     *This is a short method made purely to increase readability and reduce the amount of code required.
     *It will return true if the given character is one of the 4 basic mathematical operations
     *
     *@param c	The character to be tested.
     *
     *@return 	True if the character is one of the 4 basic mathematics operations
     */
    private static boolean isOperator(char c) {
        if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '%') {
            return true;
        }
        return false;
    }

    /**
     *Checks to see whether a string counts as a number (with decimals allowed).
     *
     *@param str		The string of the "number" to be tested
     *
     *@return			True if the number could be parsed to a Double successfully
     */
    public static boolean isNumber(String str) {
        try {
            Double.parseDouble(str);
            return true;
        }catch (NumberFormatException nfe){
            return false;
        }
    }

    /**
     *Returns the priority of the given operator.
     *The higher the priority, the sooner the operation should be executed
     *
     *@param operator	The operator who's priority is returned.
     *
     *@return				The priority of the given operator or -1 if the character is not an operator.
     */
    private static int getOperatorPriority(char operator) {
        switch (operator) {
            case ('^'):
                return 6;
            case ('%'):
                return 5;
            case ('/'):
                return 4;
            case ('*'):
                return 3;
            case ('+'):
                return 2;
            case ('-'):
                return 1;
        }
        return -1;
    }

    //========================
    //===Functional Methods===
    //========================
    /**
     *Returns a Dimension containing the info about the deepest bracket pair in the string.
     *It contains the starting point and the length of the lowest level bracket within the
     *given string. A Dimension is used in order to allow for returning to values easily.
     *
     *@param expression	The string in which a bracket should be searched for.
     *
     *@return					The starting location (as the width) and length (as the height) of the deepest
     *							bracket pair in the given string.
     */
    private static BracketData deepestBracketContents(String expression) {
        int currentDepth = 0;	//The current "depth" in terms of brackets (e.g (1 (2(3)2)1))
        int maxDepth = 0;			//This is the maximum bracket depth in the given string
        int maxDepthStart = 0;	//The location in the given string at which the deepest bracket pair starts
        String functionName = "";
        
        //Loop over characters to check for opening brackets
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '(') {
                currentDepth++;
                //If an opening bracket is found, increase the depth and max depth if required
                if (currentDepth > maxDepth) {
                    maxDepth = currentDepth;
                    maxDepthStart = i;
                }
                //If its not an opening bracket then we should check if its a closing bracket
                //If so then decrement the current depth
            } else if (expression.charAt(i) == ')') {
                currentDepth--;
            }
        }
        
        //If the bracket is the first character then it cannot possibly be a function
        if(maxDepthStart > 0){
            //Start at the bracket's begining and loop backwards to get the function name
            int i = maxDepthStart-1;
            char c = expression.charAt(i);    //The character before the '('
            
            while(Character.isLetter(c) && i>=0){
                functionName = c+functionName;
                i--;
                c = expression.charAt(i);
            }
        }
        
        int bracketLocation = maxDepthStart + 1;
        int bracketLength = expression.indexOf(")", maxDepthStart) - (maxDepthStart + 1);
        
        return new BracketData(bracketLocation, bracketLength, functionName);
    }

    /**
     *Finds the highest priority mathematical operator in a string.
     *This allows the processing of simple strings of multiple characters.
     *If multiple operations are found with the same highest priority
     *then the first one is returned.
     *
     *@param expression	The string that needs to be searched for an operator.
     *
     *@return					The location in the given string of the highest priority operator.
     */
    private static int getHighestPriorityOperatorLocation(String expression) {
        int currentPriority = 0;			//The priority of the currently examined character
        int maxPriority = 0;					//The maximum priority found in the string
        int maxPriorityLocation = -1;		//The location of the character with the highest priority

        for (int i = 0; i < expression.length(); i++) {
            if (isOperator(expression.charAt(i))) {

                //Find the priority and assign a new max priority if required
                currentPriority = getOperatorPriority(expression.charAt(i));
                if (currentPriority > maxPriority) {
                    maxPriority = currentPriority;
                    maxPriorityLocation = i;
                }
            }
        }
        return maxPriorityLocation;
    }

    /**
     *Returns a number on the left of the given location in a string.
     *This is only useful when searching for the operatands for an operator.
     *
     *@param source		The string to be searched for a number.
     *@param startLoc	The point in the string where searching starts. Note that this is included
     *						in the search so if it is not a number then the method will likely return an empty string.
     *
     *@return				The number to the left of the given location in the string, or an empty string if there is
     *						no number to the left.
     */
    private static String getNumberLeft(String source, int startLoc) {
        String number = "";		//Stores the number being compiled
        char temp;				//Temporary storage for the currently looped character, this is used for efficiency purposes - to prevent excessive charAt(i) use

        for (int i = startLoc; i >= 0; i--) {
            temp = source.charAt(i);

            //If it is an element of a number (a digit or a point) then prefix it onto the number (because we are moving right to left it has to be prefixed, otherwise the number is the wrong way around)
            if (Character.isDigit(temp) || temp == '.') {
                number = temp + number;

                //If it is a space then it can be ignored
            } else if (temp == ' ') {
                //If it is a minus then we need to check if the next character is also an operation (remember that we are busy "moving" left) because then it is a negative number, if not then it is the actual operator
            } else if (temp == '-') {
                if (i == 0 || isOperator(source.charAt(i - 1))) {
                    number = temp + number; //If there is another operation, we can add the negative because it's a negative, not an operation
                } else {
                    return number;	//Seeing as there is no other operation, then the - must be the operator, so we're finished with the number
                }
            } else {
                return number;
            }
        }
        return number;
    }

    /**
     *Returns a number on the right of the given location in a string.
     *This is only useful when searching for the operands for an operator.
     *
     *@param source		The string to be searched for a number.
     *@param startLoc	The point in the string where searching starts. Note that this is included
     *						in the search so if it is not a number then the method will likely return an empty string.
     *
     *@return				The number to the right of the given location in the string, or an empty string if there is
     *						no number to the right.
     */
    private static String getNumber(String source, int startLoc) {
        String number = "";		//Stores the number being compiled
        char temp;				//Temporary storage for the currently looped character, this is used for efficiency purposes - to prevent excessive charAt(i) use

        for (int i = startLoc; i < source.length(); i++) {
            temp = source.charAt(i);

            //If it is an element of a number (a digit or a point) then suffix it onto the number
            if (Character.isDigit(temp) || temp == '.') {
                number += temp;

                //If it is a space then it can be ignored
            } else if (temp == ' ') {
                //Unlike when we are going left, if we get to a minus sign, we need to check that the next digit is a number instead of an operation
            } else if (temp == '-') {
                if (i < source.length() && Character.isDigit(source.charAt(i + 1))) {
                    number = temp + number;
                }

            } else {
                return number;
            }
        }
        return number;
    }

    /**
     *Calculates the value of a single operation. It takes a string that consists of
     *2 numbers with an operation between them and returns the answer. in the form of
     *a double. For example "2+5" will return 7.0
     *
     *@param tempExpression	The expression containing the 2 numbers and an operator
     *@param operatorLoc        The location within the expression where the operation is situated
     *
     *@return	The result of the given operation.
     *
     *@throws	ArithmeticException - If the operation attempts to divide by zero
     */
    private static BigDecimal evaluateOperation(String tempExpression, int operatorLoc) {
        char tempHighPriorityOperator;	//The character that is the operator for the operation
        BigDecimal num1;		//The first number of the operation
        BigDecimal num2;		//The second number of the operation

        //Assign the operator to it's variable, this forms the center of the operation
        tempHighPriorityOperator = tempExpression.charAt(operatorLoc);
        
        //Get the numbers next to that operator
        //Check to see if there is a number at the start at all, it may just be something like (-1), if that happens then the first number is effectively 0 as the program doesnt allow multiplication or division with only 1 adjacent number
        if (operatorLoc == 0) {
            num1 = BigDecimal.ZERO;
        } else {
            num1 = new BigDecimal(tempExpression.substring(0, operatorLoc));
        }
        //Parse the first number if it exists, and then the second number (which must always exist, you cannot have (1-)
        num2 = new BigDecimal(tempExpression.substring(operatorLoc + 1));
        
        //Calculate the result depending on which operator is being used
        switch (tempHighPriorityOperator) {
            case ('%'):
                return num1.remainder(num2);

            case ('^'):
                double base = num1.doubleValue();
                double exponent = num2.doubleValue();
               
                if((base < 0) && (exponent != (int)exponent)){
                    throw new ArithmeticException("Negative base to a non-real power.");
                }
                return new BigDecimal(StrictMath.pow(base,exponent));

            case ('/'):
                if (num2 == BigDecimal.ZERO) {
                    //If one is dividing by zero, throw an Arithmetic Exception which can be caugth by the program
                    throw new ArithmeticException("Undefined");
                } else {
                    return num1.divide(num2, MathContext.DECIMAL128);
                }

            case ('*'):
                return num1.multiply(num2);

            case ('+'):
                return num1.add(num2);

            case ('-'):
                return num1.subtract(num2);
        }
        return BigDecimal.ZERO;
    }

    //========================
    //=====Public Methods=====
    //========================
    /**
     *Calculates the result of the given expression string.
     *The given expression has to start and end with a bracket to prevent errors.
     *This is because the method is based around brackets and uses them for
     *it's order of operations for one. It is wise to run the string through the
     *validateExpression(String) method before handing it to this one because then
     *you can be sure of it's appropriateness.
     *
     *@param expression	The string who's mathematical value should be resolved.
     *
     *@return					The value of the given mathematical expression.
     */
    public static String evaluateExpression(String expression) throws ArithmeticException {
        String tempExpression;              //This is the "sub-expression" that the program is currently working with (the current bracket, effectively). Can consist of many numbers and operation
        String tempCalculation;             //This is used to store single calculations as they are being carried out (e.g 2 numbers with an operation in between)
        int tempHighPriorityOperatorLoc;    //This is the location of the operator in the current expression with the highest priority (e.g division has a higher priority than addition)
        char tempHighPriorityOperator;      //This is the actual character of the operator
        BigDecimal result;                  //This is the "result" of the expression being worked with (e.g 5+3-1 would give a result of 7)
        BracketData deepBracketData;        //This is used to temporarily store the values of the so-callsed "deep bracket" (the "lowest level" bracket in the expression) start and length
        
        //Remove any possible spaces from the expression
        expression = expression.replaceAll(" ","");
        
        //Ensure that the expression is surrounded by brackets on the very ends
        if (expression.charAt(0) != '(' || expression.charAt(expression.length()-1) != ')') {
            expression = "(" + expression + ")";
        }

        //Get the location of the deepest pair of brackets in the expression
        deepBracketData = deepestBracketContents(expression);
        //Store the individual bits of immediately important information
        //deepBracketLocation = tempD.location;
        //deepBracketLength = tempD.length;

        //Use the deep bracket information to extract the required sub-expression
        tempExpression = expression.substring(deepBracketData.location, deepBracketData.location + deepBracketData.length);
        //Get the location and value of the highest priority operation in that sub-expression
        //A while loop is used so as to allow for many different operations in a single bracket
        while ((tempHighPriorityOperatorLoc = getHighestPriorityOperatorLocation(tempExpression)) >= 0) {
            
            tempHighPriorityOperator = tempExpression.charAt(tempHighPriorityOperatorLoc);
            //Ensure that the number is small enough so that it it doesnt have an "E" in it (exponent)
            if (tempExpression.indexOf("E") >= 0) {
                System.out.println("Found an E: "+tempExpression + " in "+expression + " for operator: "+tempHighPriorityOperator+ " at location "+tempHighPriorityOperatorLoc);
                throw new ArithmeticException("The number used in a calculation was too larger (contains \"E\").");
            }

            //This is the current single operation that is being carried out within the current sub-expression
            tempCalculation = getNumberLeft(tempExpression, tempHighPriorityOperatorLoc - 1) + tempHighPriorityOperator + getNumber(tempExpression, tempHighPriorityOperatorLoc + 1);
            
            //Compute the result of the abovementioned calculation and replace it's previous components (the 2 numbers and operation) with it's result
            //The If-statement allows a more efficient operation by not re-inserting the piece of the string
                //that came before/after the operation when not needed (IE when there is nothing else)
            //Note that in all of these method calls, we dont use the tempHighPriorityOperatorLoc variable for the
                //operator location because it is the location in the calculation, where as the variable is the
                //location in the temporary expression
            if (tempExpression.length() == tempCalculation.length()) {
                tempExpression = evaluateOperation(tempCalculation, tempCalculation.indexOf(tempHighPriorityOperator)).toPlainString();
            
            }else{
                int calcLoc = tempExpression.indexOf(tempCalculation);
                
                if(calcLoc == 0){
                    tempExpression = evaluateOperation(tempCalculation, tempCalculation.indexOf(tempHighPriorityOperator)).toPlainString()
                            + tempExpression.substring(calcLoc + tempCalculation.length());

                } else {
                    tempExpression = tempExpression.substring(0,calcLoc) 
                            + evaluateOperation(tempCalculation, tempCalculation.indexOf(tempHighPriorityOperator))
                            + tempExpression.substring(calcLoc + tempCalculation.length());
                }
            }
            //Check to see if there is another operation that can be done. This must be done here in addition to at the start of the loop, because here it will not take into account an operation before the first digit (e.g in -2) but that has to happen in the start of the loop so as to remove plus signs
            if (getHighestPriorityOperatorLocation(tempExpression.substring(1)) == -1) {
                break;
            }
        }

        //Convert our string result into a double
        result = new BigDecimal(tempExpression);

        //If the bracket we're currently dealing with is a function, then run the function before continuing
        if(deepBracketData.isFunction){
            result = FunctionManager.resolveFunction(deepBracketData.function, result);
            
            //Re-insert the result into the initial expression, removing the function. This replaces the components that made up the calculation, with it's answer thereby reducing the number of terms in the expression by 1 but keeping the same value
            tempExpression = expression.substring(0, deepBracketData.location - 1-deepBracketData.function.length())
                + result.toPlainString()
                + expression.substring(deepBracketData.location + deepBracketData.length + 1);
        }else{
            //Re-insert the result into the initial expression. This replaces the components that made up the calculation, with it's answer thereby reducing the number of terms in the expression by 1 but keeping the same value
            tempExpression = expression.substring(0, deepBracketData.location - 1)
                + result.toPlainString()
                + expression.substring(deepBracketData.location + deepBracketData.length + 1);
        }

        
        //Check to see whether or not there are other brackets in the initial expression and if so, start the entire process all over again
        //I <3 Recursion
        if (tempExpression.indexOf('(') > -1) {
            tempExpression = evaluateExpression(tempExpression);
        }

        //Check to see whether or not there are any leftover signs (+ or -) that shouldnt be there and resolve them
        //into the correct value as necessary
        if (tempExpression.lastIndexOf("+") > -1) {
            tempExpression = tempExpression.substring(1);
        }
        if (tempExpression.lastIndexOf("-") > 0) {
            tempExpression = tempExpression.substring(1);
        }

        return tempExpression;
    }
    
    public double evaluateExpressionDouble(String expression){
        return new BigDecimal(expression).doubleValue();
    }

    /**
     *Checks the validity of the given expression string.
     *This ensures that the expression is suitable for
     *the program to evaluate it and acquire it's result.
     *
     *@param expression	This is the expression that needs to be validated
     *
     *@return An empty string if the expression is suitable for the program and
     *			meets all the requirements.
     */
    public static String validateExpression(String expression) {
        int bracketCount = 0;		//The number of current brackets awaiting "partners"
        char c;							//The currently looped character
        boolean operation = false;	//Whether or not we just found an operation
        String error = "";			//The error message that describes what is wrong with the expression

        //Ensure that it starts with either a number or a - and ends with a number
        if (!(Character.isDigit(expression.charAt(0)) || (expression.charAt(0) == '-') || (expression.charAt(0) == '('))) {
            error += "The expression must start with a number and it may not begin with a plus sign\n";
            return error;
        }
        if (!(Character.isDigit(expression.charAt(expression.length() - 1)) || (expression.charAt(expression.length() - 1)) == ')')) {
            error += "The expression must end with a number\n";
            return error;
        }

        //Loop over every character in the expression
        for (int i = 0; i < expression.length(); i++) {
            c = expression.charAt(i);

            switch (c) {
                case ('+'):
                case ('-'):
                case ('*'):
                case ('/'):
                case ('^'):
                case ('%'):
                    operation = true;
                    break;
                case ('('):
                case (')'):
                case ('.'):
                case (' '):
                    operation = false;
                    break;

                //If it is either a digit or an unrecognized symbol
                default:
                    if (!(Character.isDigit(c))) {
                        error += "The expression contains an unrecognized symbol: " + c + "\n";
                    } else {
                        operation = false;
                    }
            }

            //Check for multiple operations
            if (operation) {
                switch (expression.charAt(i + 1)) {
                    case ('+'):
                    case ('*'):
                    case ('/'):
                        error += "The expression contains multiple incompatible operations in a row.\n";
                }
            }

            //Count brackets
            if (c == '(') {
                bracketCount++;
            } else if (c == ')') {
                bracketCount--;
            }
        }

        //Check for correct usage of brackets
        if (bracketCount < 0) {
            error += "The expression contains too many closing brackets\n";
        } else if (bracketCount > 0) {
            error += "The expression contains too many opening brackets\n";
        }

        return error;
    }
}
